package com.wtgroup.demo.mianshi.算法.第k小数;

import com.wtgroup.demo.common.util.ABTest;
import com.wtgroup.demo.common.util.RandomUtil;
import com.wtgroup.demo.common.util.Tools;

import java.util.Arrays;


/**
 * @author nisus
 * @version 0.1
 * @since 2023/5/21 10:36
 */
public class D_TopK {

    public static void main(String[] args) {
        // Judger.of(() -> {
        //     int[] arr = RandomUtil.randomArray(RandomUtil.randomInt(1, 100), 0, 1000);
        //     int[] copy1 = Arrays.copyOf(arr, arr.length);
        //     int[] copy2 = Arrays.copyOf(arr, arr.length);
        //     int k = RandomUtil.randomInt(0, arr.length) + 1;
        //
        //     m_sort(copy1, k);
        //     func(copy2, k);
        //     return Tools.equals(copy1, copy2);
        // }).start().print();

        testP();
    }

    /**
     * sort            heap            -
     * 248毫秒  386毫秒  -138
     * ---
     * iter: 10
     */
    private static void testP() {
        ABTest abTest = new ABTest("sort", "heap");
        for (int i = 0; i < 10; i++) {
                int[] arr = RandomUtil.randomArray(RandomUtil.randomInt(1, 100_0000), 0, 1000);
                int[] copy1 = Arrays.copyOf(arr, arr.length);
                int[] copy2 = Arrays.copyOf(arr, arr.length);
                int k = RandomUtil.randomInt(0, arr.length) + 1;

                abTest.runA(() -> m_sort(copy1, k));
                abTest.runB(() -> func(copy2, k));
        }
        abTest.print();
    }

    static int[] m_sort(int[] arr, int k) {
        // Integer[] integers = Tools.int2IntegerArray(arr);
        // Arrays.sort(integers, (o1, o2) -> (Integer)o2 - (Integer)o1);
        Arrays.sort(arr);
        // return Tools.integer2IntArray(Arrays.copyOf(integers, k));
        int[] ret = new int[k];
        int len = arr.length;
        for (int i = 0; i < k; i++) {
            ret[i] = arr[len - 1 - i];
        }
        return ret;
    }


    static int[] func(int[] arr, int k) {
        // top k, 用小根堆
        int[] heap = new int[k];
        int heapSize = 0;
        // 模拟流数据
        boolean heaped = false;
        for (int i = 0; i < arr.length; i++) {
            if (heapSize < k) {
                heap[heapSize] = arr[i];
                heapSize++;
                continue;
            }

            if (heaped == false) {
                // 已有的 堆化
                for (int j = heapSize/2-1; j >= 0; j--) {
                    siftDown(heap, heapSize, j);
                }
                heaped = true;
            }
            // 堆顶删除
            if (arr[i] > heap[0]) {
                heap[0] = arr[i];
                siftDown(heap, heapSize, 0);
            }
        }

        if (heaped == false) {
            for (int j = heapSize/2-1; j >= 0; j--) {
                siftDown(heap, heapSize, j);
            }
            heaped = true;
        }

        for (int size = heap.length; size > 0; size--) {
            Tools.swap(heap, 0, size- 1);
            siftDown(heap, size - 1, 0);
        }

        return heap;
    }

    private static void siftDown(int[] heap, int size, int curr) {
        int bak = heap[curr];
        int childIx;
        while ((childIx = 2 * curr + 1) < size) {
            if (childIx + 1 < size && heap[childIx + 1] < heap[childIx]) {
                childIx = childIx + 1;
            }
            if (bak < heap[childIx]) {
                break;
            }
            heap[curr] = heap[childIx];
            curr = childIx;
        }
        heap[curr] = bak;
    }


}
